Graphe complet

Définition

Un graphe simple est dit complet si tous ses sommets sont adjacents, c’est-à-dire si toutes
les arêtes possibles entre deux sommets (sauf les boucles) existent.

Remarque

Il y a un seul graphe simple complet à  \(n\) sommets, noté \(K_n\)

Exemple

Voici le graphe  \(K_5\) :

Propriété  

Dans un graphe simple complet d'ordre  \(n\) , le degré de chaque sommet est égal à  \(n-1\) .
Le nombre d'arêtes de \(K_n\)  est donc  \(\dfrac {n(n-1)}{2}=\begin{pmatrix}n\\2\end{pmatrix}\) .